#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>

//char* longestCommonPrefix(char** strs, int strsSize) {
//    char* ans = (char*)malloc(sizeof(char) * 200);
//    int i = 0;
//    strcpy(ans, strs[0]);
//    while (i < strsSize)
//    {
//        int j = 0;
//        while (strs[i][j] != '\0' && ans[j] != '\0')
//        {
//            if (strs[i][j] != ans[j])
//            {
//                break;
//            }
//            j++;
//        }
//        ans[j] = '\0';
//        i++;
//    }
//    return ans;
//}

char pairs(char a) {
    if (a == '}') return '{';
    if (a == ']') return '[';
    if (a == ')') return '(';
    return 0;
}

bool isValid(char* s) {
    int n = strlen(s);
    if (n % 2 == 1) {
        return false;
    }
    int stk[n + 1], top = 0;
    for (int i = 0; i < n; i++) {
        char ch = pairs(s[i]);
        if (ch) {
            if (top == 0 || stk[top - 1] != ch) {
                return false;
            }
            top--;
        }
        else {
            stk[top++] = s[i];
        }
    }
    return top == 0;
}